This invention relates generally to a protocol used in interconnected computer networks known as distance vector routing and, more specifically, to distance vector routing for use in interconnected networks having point-to-point links for transmission of messages in a "datagram" environment. Before these terms can be meaningfully discussed, some background concerning communication over computer networks is needed.
To make computer networking more manageable, network functions are commonly partitioned using a layering concept. Application-to-application data transfer between two interconnected computers or "nodes" in a network is accomplished by logically building functions in a series of layers, where each layer uses the services of the layer immediately below, adds functions of its own, and presents a richer service to the layer immediately above. Each layer in a node that is the source of a message or information packet logically communicates with its peer layer in a destination node, but does so by using the services of the layer immediately below.
The present invention concerns only the bottom three layers, commonly known as:
1. The physical layer, which includes mechanical, electrical, optical, functional and procedural properties for bit stream transmission across physical connections between data link entities.
2. The data link layer, which provides multiplexing, framing of the physical layer bit stream into messages, error detection, physical channel management and possibly other functions.
3. The network layer, which deals with creating paths through the network, involving many series of data link layer "hops."
There are two types of services that a layer can provide:
(i) "Reliable"--In this type of service, delivery of data in the order sent is guaranteed. The layer numbers messages, receives acknowledgments from destination nodes, and retransmits messages that have been lost or damaged. PA1 (ii) "Datagram"--In this type of service, data transfer is not guaranteed to be reliable. The layer transmits data, and does not receive confirmation from the recipients that the data have been correctly received.
Originally, data link layer protocols were designed for point-to-point links, i.e. direct connections between pairs of nodes. The data link layer protocols designed for point-to-point links provided reliable service. Then Local Area Networks (LANs) were developed, enabling many nodes to be connected to a single "wire" or physical transmission medium. The development of LAN technology made datagram service the more natural choice of service. Recently, datagram data link protocols for point-to-point links have become popular. An example of a datagram point-to-point protocol is PPP.
Certain protocols, among them being distance vector routing, require that the latest piece of data get delivered correctly, but do not require that every piece of data get delivered. In other words, if new data supersede old data, it is not necessary, under these protocols, for the old data to be delivered. For such protocols, a reliable service is not the most efficient choice, because it will persist in transmitting old data even if new data is available for transmission. Transmission of old data in this situation is not only an unnecessary use of available bandwidth, but also slows down delivery of the new data, because the new data will not be delivered by a reliable service until all the previous old data have been successfully transmitted. On the other hand, conventional datagram service is not a good choice either, because the latest data must be delivered in a timely and efficient manner (unless superseded by later data).
An example of such a protocol, requiring that the latest data be delivered but not necessarily any older data, is a particular type of Network Layer protocol known as distance vector routing. It is used by DECNET Phase IV, as well as other Network Layer protocols, such as RIP. In this protocol, each router node X is responsible for informing each of X's neighbors about X's distance to each destination in the network. X calculates its own distance to each destination based on its neighbor's reported distances to that destination. Thus X's distance to a particular destination must be reliably delivered to each neighbor, unless X's recomputation of its distances results in a different distance to that destination before the previous value is successfully transmitted. In this case the previous value need not be transmitted, and instead the new value must be transmitted.
As outlined above, a significant problem with a conventional distance vector routing protocol is that, if the data link layer provides datagram service to the network layer, the protocol has no way of ensuring that updated distance vectors will reach their destinations. One solution that has been proposed is to have each router retransmit its distance vector to neighboring routers on a periodic basis, whether or not any changes have occurred in the distance vector. The theory underlying this approach is that if any updated distance vector does not reach its destination, the likelihood is that the next periodic transmission will be made without error. This approach is used in a datagram data link layer protocol known a PPP (for point-to-point protocol). Its principal disadvantage is that it incurs unnecessary overhead. Distance vectors are updated whether or not they have changed, which results in significant unnecessary message traffic between routers. The approach has also been applied to local area networks, as distinguished from point-to-point links, since it was once perceived that the bandwidth of LANs was abundant.
An alternative approach is to provide reliable service for this type of router traffic only, but this also poses some significant difficulties. If reliable service is not needed for normal data message traffic, there has to be some way of distinguishing the distance vector traffic from normal data packets. Moreover, with reliable service, each time an information packet with updated distance vector data was transmitted, the transmitting router would be forced to retain the packet until an acknowledgment was received. Having to retain multiple packets until acknowledgments are received is an inefficient use of data storage facilities. An additional drawback is that, if the distance vector changes before an acknowledgment is received, a new update could not be immediately transmitted by the router, which must wait until the prior update is acknowledged.
It will be appreciated from the foregoing that there is still a need for improvement in the way that distance vectors are transmitted between routers in a network. Specifically, what is needed is some way of making sure that all routers connected by point-to-point datagram links will receive updates to distance vectors in a timely and efficient manner, but without the unnecessary burden of mandatory periodic transmission of data, and without the drawbacks associated with adding reliable service. The present invention is directed to this end.